package com.howtoplayalgorithm.dynamicprogramming;

/**
 * 数字三角形
 */
public class NumberPyramid {

    static int[][] cache;

    //记忆型动规程序。
    public static int numberPyramidSimple(int[][] pyramid,int x,int y){
        cache = new int[x][y];
        int res = numberPyramidSimpleInner(0,0,pyramid);
        return res;
    }

    private static int numberPyramidSimpleInner(int x, int y, int[][] pyramid) {
        int self = pyramid[x][y];

        if(x >= pyramid.length - 1){
            if(y < pyramid[x].length) {
                //最底层不缓存。
                return self;
            }
            return 0;
        }

        int left,right;

        if(cache[x + 1][y] != 0){
            left = cache[x + 1][y];
        }else{
            left = numberPyramidSimpleInner(x + 1,y,pyramid);
            cache[x + 1][y] = left;
        }
        if(cache[x + 1][y + 1] != 0){
            right = cache[x + 1][y + 1];
        }else{
            right = numberPyramidSimpleInner(x + 1,y + 1,pyramid);
            cache[x + 1][y + 1] = right;
        }

        return Math.max(self + left,self + right);
    }

    //递推型动规程序，人人为我（空间未优化）
    //人人为我的前提： 1.最后一层子问题比较好找寻，数量有限，2. 想要空间优化时，要求无后效性。
    //人人为我的优势之处：由于一定是计算出下层，再去计算上层，因此在空间上，可以减少存储量（只需要存下每一层的结果即可）
    //而传统记忆型动规，由于是深度优先的，因此每次子问题方法调用时都会有一个从1层到最深层的过程，导致之前子问题算出来的最深层在被计算完一次后，其结果仍然可能被之后任意子问题用到，
    //因此无法减少存储量。
    //
    public static int numberPyramidSimpleRRWW(int[][] pyramid,int x,int y){
        cache = new int[x][y];
        numberPyramidSimpleInnerRRWW(pyramid.length - 1,pyramid);
        return cache[0][0];
    }

    private static void numberPyramidSimpleInnerRRWW(int i, int[][] pyramid) {

        if(i <= -1){
            return;
        }

        if(i < pyramid.length - 1){
            //其他层，根据上一层的来算
            for (int y = 0; y < pyramid[i].length; y++) {
                int tmp = pyramid[i][y];
                cache[i][y] = Math.max(tmp + cache[i + 1][y],tmp + cache[i + 1][y + 1]);
            }
        }else {
            //最后一层，直接放结果
            for (int y = 0; y < cache[i].length; y++) {
                cache[i][y] = pyramid[i][y];
            }
        }

        numberPyramidSimpleInnerRRWW(i - 1,pyramid);
    }

    //递归向动规的转化，与尾递归

    /**
     * 递归中，每个阶段一定存在    上一阶段状态，状态转换方程，这一阶段的结果。
     * 递归到动规（人人为我） 可以看成，把上一阶段的结果放在了数组中，并作为参数传给了这一阶段，这一阶段计算出结果，并把它放到了数组中，作为下一阶段的条件。
     *
     * 这种 人人为我  和普通动规不同点在于，   上一阶段的条件可以推出所有这一阶段的结果（并且也是下一阶段的结果）
     * 这是一种和普通动规截然不同的思路,人人为我的这种模型可以用来做尾递归，因为下一阶段所要用的所有条件凭借这个阶段的一次方法调用就能给出。
     *
     * 以下为斐波那契数列递归的例子
     */
    public static int fbnq(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return fbnqInner(n - 2,1,2);

    }

    private static int fbnqInner(int n, int first, int second) {
        n --;
        if(n == 0){
            return first + second;
        }
        return fbnqInner(n,second,first + second);
    }

    public static void main(String[] args){

        int[][] test = {{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5}};

        int res = numberPyramidSimpleRRWW(test,5,5);
        System.out.println(res);

        System.out.println(fbnq(5));
    }

}
